UVa/410 - Station Balance/410.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 //_for(i, a, b):  a <= i < b
  22 #define _for(i, a, b) for (int i=a, _n = b; i<_n; ++i)
  23 //_from(i, a, b): a > i >= b
  24 #define _from(i, a, b) for (int i=a-1, _n = b; i>=_n; --i)
  25
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 struct state{
  29   int used, chamber, sum;
  30   state(){}
  31   state(int used, int i, int s) : used(used), chamber(i), sum(s){}
  32
  33   bool operator <(const state &that) const {
  34     return sum > that.sum || (sum == that.sum && chamber < that.chamber);
  35   }
  36 };
  37
  38 const int oo =  INT_MAX / 4;
  39 int p[10];
  40 int d[1<<11][6], choice[1<<11][6];
  41
  42 #define enqueue(new_used, new_i, new_w, c)      \
  43   if (new_w < d[new_used][new_i]){              \
  44     d[new_used][new_i] = new_w;                 \
  45     choice[new_used][new_i] = c;                \
  46     q.push(state(new_used, new_i, new_w));      \
  47     if (0) printf("   pushed used=%x, i=%d, w=%d\n", new_used, new_i, new_w); \
  48   }
  49
  50 int binary(int i){
  51   for (unsigned int mask = 1 << 10; mask; mask >>= 1){
  52     cout << (i & mask ? "1" : "0");
  53   }
  54 }
  55
  56
  57 int main(){
  58
  59   int n, m, i, j, k, Set = 1;
  60   while (cin >> n >> m){
  61     int mass = 0;
  62     for (i=0; i<m; ++i)
  63       cin >> p[i], mass += p[i];
  64
  65     for (i=0; i<(1<<m); ++i)
  66       for (j=0; j<=n; ++j)
  67         d[i][j] = oo;
  68
  69     priority_queue<state> q;
  70     q.push(state(0, 0, 0));
  71     while (q.size()){
  72       int used = q.top().used;
  73       int i = q.top().chamber;
  74       int w = q.top().sum;
  75
  76
  77       /*
  78       printf("popped used=%x, i=%d, w=%d\n", used, i, w);
  79       binary(used);
  80       printf("\n");
  81       */
  82
  83       q.pop(); //!
  84
  85       if (i == n && used == (1 << m) - 1){
  86         //Solved!
  87         printf("Set #%d\n", Set++);
  88
  89
  90
  91         int mask = used;
  92
  93         for (j=n; j>0; --j){
  94           printf("%2d:", n-j);
  95
  96           for (k=0; k<m; ++k){
  97             if (choice[mask][j] & (1 << k)) printf(" %d", p[k]);
  98           }
  99           printf("\n");
 100
 101           mask &= ~choice[mask][j];
 102         }
 103
 104         printf("IMBALANCE = %.5lf\n\n", 1.0 * w / n);
 105         break;
 106       }
 107
 108       if (i > n || w > d[used][i]) continue;
 109
 110       enqueue(used, i+1, w + mass, 0);
 111       for (j=0; j<m; ++j){
 112         if ( ! (used & (1 << j)) ){
 113           int w_extra = abs(n*p[j] - mass);
 114           enqueue(used | (1 << j), i+1, w + w_extra, (1 << j));
 115
 116           for (k=0; k<m; ++k)
 117             if (k != j && ( ! (used & (1 << k)) )){
 118               w_extra  = abs(n*(p[j]+p[k]) - mass);
 119               enqueue(used | (1 << j) | (1 << k), i+1, w + w_extra, (1 << j) | (1 << k));
 120             }
 121         }
 122       }
 123     }
 124
 125   }
 126
 127   return 0;
 128 }